//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {
    public static void main(String[] args) {
        //1.BM16 删除有序链表中重复的元素-II
        public ListNode deleteDuplicates (ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode newHead = new ListNode(-1);
            newHead.next = head;
            ListNode cur = newHead;
            while(cur.next != null && cur.next.next != null) {
                //遇到相邻两个节点值相同
                if(cur.next.val == cur.next.next.val) {
                    int tmp = cur.next.val;
                    //将所有相同的都跳过
                    while(cur.next != null && cur.next.val == tmp) {
                        cur.next = cur.next.next;
                    }
                } else {
                    cur = cur.next;
                }
            }
            return newHead.next;
        }
        //2.BM5合并k个已排序的链表
        public ListNode mergeKLists (ArrayList<ListNode> lists) {
            //创建一个小根堆
            Queue<ListNode> queue = new PriorityQueue<>((v1, v2)-> v1.val - v2.val);
            //遍历所有链表的第一个元素也就是链表的表头
            for (int i = 0; i < lists.size(); i++) {
                //不为空则加入小根堆
                if(lists.get(i) != null) {
                    queue.add(lists.get(i));
                }
            }
            //创建一个傀儡节点
            ListNode newHead = new ListNode(-1);
            ListNode head = newHead;
            //直到小根堆为空
            while(!queue.isEmpty()) {
                //取出小根堆中最小的元素
                ListNode tmp = queue.poll();
                head.next = tmp;
                head = head.next;
                //每一次取出链表的后一个元素加入小根堆
                if(tmp.next != null) {
                    queue.add(tmp.next);
                }
            }
            return newHead.next;
        }
    }
}